package day_2022_9_to_12.Day;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/09/07 18:37
 **/
public class Day5_6_Interview59_MaxQueue {
    class MaxQueue {
        Deque<Integer> q1;
        Deque<Integer> q2;
        public MaxQueue() {
            q1 = new LinkedList<>();
            q2 = new LinkedList<>();
        }

        public int max_value() {
            return q2.isEmpty() ? -1 : q2.peek();
        }

        public void push_back(int value) {
            q1.offer(value);
            while(!q2.isEmpty() && q2.peekLast() < value) q2.pollLast();
            q2.offer(value);
        }

        public int pop_front() {
            if(q1.isEmpty()) return -1;
            int val = q1.pop();
            if(q2.peek() == val) q2.pop();
            return val;
        }
    }
}